#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+10;
int n,m,k,maxl,a[MAXN],ans[MAXN],c[MAXN];
struct node
{
	int l,r,num;
	bool operator<(const node b)const
	{
		return l/maxl==b.l/maxl?r<b.r:l/maxl<b.l/maxl;
	}
}qu[MAXN];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&qu[i].l,&qu[i].r);
		maxl=max(maxl,qu[i].l);
		qu[i].num=i;
	}
	sort(qu+1,qu+1+m);
	int l=1,r=0,temp;
	for(int i=1;i<=m;++i)
	{
		while(r<qu[i].r)
		{
			++r;
			temp+=2*c[a[r]]+1;
			++c[a[r]];
		}
		while(l>qu[i].l)
		{
			--l;
			temp+=2*c[a[l]]+1;
			++c[a[l]];
		}
		while(r>qu[i].r)
		{
			temp-=2*c[a[r]]-1;
			--c[a[r]];
			--r;
		}
		while(l<qu[i].l)
		{
			temp-=2*c[a[l]]-1;
			--c[a[l]];
			++l;
		}
		ans[qu[i].num]=temp;
	}
	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}
